The present invention relates generally to a data processing system such as a multiprocessor system which comprises a plurality of processors and a main memory common to the individual processors. More particularly, the invention is concerned with a cache memory controlling method and an apparatus for controlling the invalidating or purging of a cache memory or memories.
Data stored in the main memory is mapped to a cache memory on a block-by-block basis. In that case, the cache memory is provided with an address array (also referred to as a directory) which serves to hold addresses of corresponding main memory blocks.
When reference is made to the main memory by the processing apparatus or processor, the address for the reference is first compared with an address registered in the address array. When coincidence is found as a result of the comparison, then the corresponding block within the cache memory is referred to. Thus, the access time can be shortened. Parenthetically, a scheme for mapping a given or arbitrary main memory block or column to a given or arbitrary cache memory block is called a full associative scheme, and a scheme for mapping a main memory column to a cache memory block in one-to-one corresponding relation is called a direct mapping scheme. Further, mapping of a column on the main memory to one of a set of blocks of the cache memory is referred to as "set associative mapping".
In a multiprocessor system in which the main memory is shared in common among a plurality of processors which each have a private cache memory, it is required that the contents of the cache memories associated with the individual processors, respectively, be constantly up-to-date. Accordingly, when the content of a block in one cache memory is to be updated (or rewritten), all other cache memories have to be invalidated for that particular block. In this conjunction, it is noted that a block to be invalidated may contain up-to-date data. In that case, it is necessary to write back that block to the main memory from the cache memory in precedence to the invalidation of the latter.
One cache memory invalidation controlling system known heretofore is described in JP-A-62-214453, by way of example. Referring to FIG. 12 of the accompanying drawings, in the case of this prior art system, there are provided a logical tag memory (or logical address array) 71 and a physical tag memory (or physical address array) 72 which are accessed with a logical address for controlling the cache memory, such that the invalidation processing can be speeded up with the aid of these memories. Incidentally, the cache memory itself is omitted from the illustration in FIG. 12.
Referring to FIG. 12, a description will be made of the address registering operation to the tag memories 71 and 72. When the access made with a certain logical address results in a mishit in the cache memory, then a new block is read out from the main memory to be transferred to the processor. In parallel therewith, the new block inclusive of the address thereof is registered in the cache memory. To this end, there are registered in the logical tag memory 71 the 13th to 31st bits (19 bits) of the logical address (32 bits) in the logical address register 15 in correspondence to a set (address) of the 4th to 12th bits (9 bits) consisting of eight bits for the intra-page address plus one bit for the page address, while there are registered in the physical tag memory 72 the 12th to 23rd bits (12 bits in total) of the physical address (24 bits) after the address translation by an address translating part 75 in correspondence to the same set address. Registration at the same set address may be realized by supplying the same logical address to both the tag memories 71 and 72 from a logical address register 15 through a multiplexer 73.
Next, description will be turned to the invalidation processing control. An invalidating address sent from another processor is set at an address input register 17. Since the 4th to 11th bits of this set address represent the intra-page offset address for which the physical address and the logical address are identical with each other, the 4th to 11th bits are inputted intact to the physical tag memory 72 through the multiplexer 73. In contrast, the 12th bit has a value which can not be determined on the basis of the 12th bit of the physical address. For this reason, a value of "0" is generated by a counter 74 as the value of the 12th bit, whereon the physical tag memory 72 is read out for comparison with the 12th to 23rd bits (12 bits in number) of the address input register 17 by a comparator 77. When coincidence is found in the comparison, a controller 76 effects the invalidation processing after resetting the flag of the relevant block of the logical tag memory 71 to "0". On the other hand, when a discrepancy is detected from the comparison, a value "1" is generated by the above-mentioned counter 74 as the value of the 12th bit for thereby making access to the physical tag memory 72. In that case, since the logical address and the set address overlap each other for one bit, there are required two count operations by the counter and twice the number of access operations. However, when the overlap between the logical address and the set address extends over two or more bits, it is necessary to set the bit number of the counter to be equal to the bit number of the overlap, to thereby perform the access operation a number of times while performing the count operation for a corresponding number of times. More specifically, for an overlap over two bits, there are required four (2.sup.2 =4) access operations at maximum. Similarly, for an overlap over three bits, eight (2.sup.3 =8) access operations at maximum must be performed, while an overlap over four bits makes it necessary to perform the access operation sixteen times (2.sup.4 =16) at maximum.
As will be appreciated from the above, in the case of the prior art system, when the number of bits over which the page address included in the logical address and the set address overlap each other is increased as a result of increasing the capacity of the cache memory, the number of times the physical tag memory has to be accessed for effectuating the block invalidation processing of the cache memory is increased correspondingly. This means in turn that the increase in the number of bits by one for designating an entry in the cache memory involves twice as many entries in the cache memory. In that case, the number of times the physical tag memory has to be accessed is increased from two to four at maximum. More concretely, when the capacity of the cache memory is doubled, the number of times the physical tag memory is accessed is also doubled. Thus, there arises a problem that the time taken for the block invalidation processing of the cache memory is undesirably increased. Incidentally, there are disclosed in U.S. Ser. No. 07/525,080 filed May 17, 1990 and assigned to the same assignee as the present application and JP-A-62-80742 laid open on Apr. 14, 1987 approaches for reducing the overhead involved in the cache memory control by decreasing the number of times a tag memory (i.e. address array of a cache memory) is accessed in a cache memory control system of the set associative mapping type.